11430. Расстояние
на дереве I
Задано дерево, состоящее из n вершин.
Для каждой вершины определите
максимальное расстояние до любой другой вершины.
Вход. Первая строка содержит целое
число n (1 ≤ n ≤ 2 * 105) – количество
вершин в дереве. Вершины пронумерованы от 1 до n.
Следующие n – 1 строк
содержат описание рёбер: каждая строка состоит из двух целых чисел a и b
(1 ≤ a, b ≤ n), обозначающих, что между
вершинами a и b существует ребро.
Выход. Выведите n целых чисел –
для каждой вершины от 1 до n максимальное расстояние до любой другой
вершины в дереве.
|
Пример
входа |
Пример
выхода |
|
5 1 2 1 3 3 4 3 5 |
2 3 2 3 3 |
РЕШЕНИЕ
графы –
поиск в глубину
Анализ алгоритма
С помощью двух запусков поиска в глубину найдём диаметр
дерева.
Поскольку дерево – это связный граф без циклов, как поиск в глубину (DFS),
так и поиск в ширину (BFS) корректно находят кратчайшие расстояния от стартовой
вершины до всех остальных.
Обозначим через a и b две вершины, находящиеся на максимальном расстоянии друг
от друга – то есть
образующие диаметр дерева.
Вычислим кратчайшие расстояния от вершины a до всех
остальных и сохраним их в массиве dista, а от вершины b – в массиве distb.
Тогда для каждой вершины i наибольшее расстояние до другой вершины будет равно
max(dista[i], distb[i])
Пример
Рассмотрим дерево
из примера.
Диаметром дерева
может быть, например, путь между вершинами 2 и 5.
Реализация алгоритма
Входное дерево хранится в виде списка смежности g.
Кратчайшие расстояния от вершин a и b сохраняются в массивах dista
и distb.
vector<vector<int>> g;
vector<int> dista, distb;
Функция dfs
выполняет поиск в глубину из вершины v.
·
Параметр d обозначает кратчайшее расстояние от
источника до вершины v.
·
Результаты сохраняются в массиве dist.
·
Параметр p указывает на предка вершины v в
процессе обхода.
void dfs(int v, int d, vector<int>&
dist, int p = -1)
{
Заносим в dist[v]
кратчайшее
расстояние от источника до вершины v.
dist[v] = d;
Перебираем все ребра (v, to). Для каждого сына to вершины v (вершина to не является предком вершины v) запускаем поиск в
глубину.
for (int to : g[v])
if (to != p)
dfs(to, d + 1, dist, v);
}
Основная часть программы. Читаем входные данные.
scanf("%d", &n);
g.resize(n
+ 1);
dista.resize(n
+ 1);
distb.resize(n
+ 1);
Строим неориентированное дерево.
for (i = 1; i < n; i++)
{
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
Находим кратчайшие расстояния от вершины 1. Самой удалённой от неё вершиной
является вершина a.
dfs(1,
0, dista, -1);
a =
max_element(dista.begin() + 1,
dista.begin() + n + 1) - dista.begin();
Затем вычисляем кратчайшие расстояния от вершины a и сохраняем их в
массиве dista. Самой удалённой вершиной от a оказывается вершина b.
Расстояние между вершинами a и b является диаметром дерева.
dfs(a,
0, dista, -1);
b =
max_element(dista.begin() + 1,
dista.begin() + n + 1) - dista.begin();
Вычисляем кратчайшие расстояния от вершины b и сохраняем их в
массиве distb.
dfs(b,
0, distb, -1);
Для каждой вершины i выводим расстояние до самой удалённой от неё
вершины.
for (i = 1; i <= n; i++)
printf("%d ", max(dista[i], distb[i]));
printf("\n");
Python реализация
import sys
sys.setrecursionlimit(1000000)
Функция dfs
выполняет поиск в глубину из вершины v.
·
Параметр d обозначает кратчайшее расстояние от
источника до вершины v.
·
Результаты сохраняются в массиве dist.
·
Параметр p указывает на предка вершины v в
процессе обхода.
def dfs(v, d, dist, p =- 1):
Заносим в dist[v]
кратчайшее
расстояние от источника до вершины v.
dist[v] = d
Перебираем все ребра (v, to). Для каждого сына to вершины v (вершина to не является предком вершины v) запускаем поиск в
глубину.
for to in g[v]:
if to != p:
dfs(to, d + 1, dist, v)
Основная часть программы. Читаем входные данные.
n = int(input())
g = [[] for _ in range(n + 1)]
dista = [0] * (n + 1)
distb = [0] * (n + 1)
Строим неориентированное дерево.
for _ in range(n - 1):
u,
v = map(int, input().split())
g[u].append(v)
g[v].append(u)
Находим кратчайшие расстояния от вершины 1. Самой удалённой от неё вершиной
является вершина a.
dfs(1, 0, dista)
a = dista.index(max(dista[1:]))
Затем вычисляем кратчайшие расстояния от вершины a и сохраняем их в
массиве dista. Самой удалённой вершиной от a оказывается вершина b.
Расстояние между вершинами a и b является диаметром дерева.
dfs(a, 0, dista)
b = dista.index(max(dista[1:]))
Вычисляем кратчайшие расстояния от вершины b и сохраняем их в
массиве distb.
dfs(b, 0, distb)
Для каждой вершины i выводим расстояние до самой удалённой от неё
вершины.
result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)